package leetcode_41_60;

import java.util.ArrayList;
import java.util.List;

public class jump_45 {
    /**
     * 题意大概是，只能跳当前格子的数字
     * 最少跳几次
     * 暂时认为情况的变化性太多
     * 必须递归中套循环暴力检索
     * 需要对递归进行剪枝，内存超出限制了
     * 剪完枝还是超出
     * @param nums
     * @return
     */
    public int jump(int[] nums) {
        if(nums.length==1)
            return 0;
        function(nums,0,0,Integer.MAX_VALUE);
        int minJumpNum=jumpAns.get(0);
        for(int i=1;i<jumpAns.size();i++)
            if(jumpAns.get(i)<minJumpNum)
                minJumpNum=jumpAns.get(i);
        return minJumpNum;
    }
    public void function(int []nums,int jumpNum,int index,int minAns){
        if(jumpNum>minAns)    //如果当前步数已经超过了之前最少步数，直接退出
            return;
        if(index>nums.length-1)
            return ;
        for(int i=nums[index];i>0;i--){    //，这里贪心跳最多步，然后递减,这样避免从小步数的大量递归跳跃
            if(index+i>nums.length-1)
                continue;
            if(index+i==nums.length-1){         //当再跳i步，直接到结尾处时，无需遍历，添加结果，返回
                if(jumpNum+1<minAns)
                    minAns=jumpNum+1;
                jumpAns.add(jumpNum+1);
                return;
            }
            if(nums[index+i]!=0){    //不能跳到值为0处
                function(nums,jumpNum+1,index+i,minAns);
            }
        }
    }
    public List<Integer> jumpAns=new ArrayList<>();

    /**
     * 想到可以反向遍历数组，进行动态规划
     * 从数组的最后一位开始，算出每一位到达末尾需要的最少跳跃次数
     * 往前遍历到第一位，即得到结果
     *
     * 比递归快多了
     * 54ms  虽然很慢，但是是我第一次自己写出通过的动态规划
     * 慢在我这样反向遍历需要对每一个元素都判断
     * 时间复杂度是数字内全体数字的和
     * @param nums
     * @return
     */
    public int jump2(int[] nums) {
        if(nums.length==1)
            return 0;
        int [] minJumpNum=new int[nums.length];   //每一节点到达末尾需要的最少跳跃次数
        //找到第一个可以跳过末尾的位置
        int idx=0;
        for(int i=nums.length-2;i>=0;i--){ //不用管倒数第一个
             if(nums.length-1<= nums[i] + i) {  //可以跳到末尾的位置
                minJumpNum[i] = 1;
                idx=i;
                break;
            }
             nums[i]=0;    //如果该节点不能到末尾，直接让位置不能被前面的跳过来
        }
        for(int i=idx;i>=0;i--){
            if(nums[i]==0) //0直接跳过
                continue;
            int range=nums[i];
            if(i+nums[i]>nums.length-1) //若跳该节点的步数最大值会超出数组范围
                range=nums.length-1-i;//直接算出可以跳几步
            int minJump=10000;
            for(int t=range;t>0;t--) {           //找出跳1步至跳nums[i]步  中最短到达结尾的总步数
                if (  nums[i + t] != 0  ||  i+t ==nums.length-1){ //末尾有可能是0
                    if (minJump > minJumpNum[i + t] + 1)    //minJumpNum[i+t]+1  即在该节点跳t步 到末尾的最少跳跃次数
                        minJump = minJumpNum[i + t] + 1;
                }
            }
            if(minJump==10000)    //说明该节点怎么跳都无法跳到末尾
                nums[i]=0; //直接赋值0
            else
                minJumpNum[i]=minJump;
        }
        return minJumpNum[0];
    }

    /**
     * 贪心算法
     *「贪心」地进行正向查找，每次找到可到达的最远位置
     *  就可以在线性时间内得到最少的跳跃次数。
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)。
     * @param nums
     * @return
     */
    public int jump3(int[] nums) {
        int length = nums.length;
        int end = 0; //当前节点能够到达的最大下标位置，记为边界
        int maxPosition = 0;    //实时等到达的最远距离
        int steps = 0;
        for (int i = 0; i < length - 1; i++) {
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if (i == end) {            //核心算法，到达最远距离后，刷新边界为maxPosition
                //不用考虑0，0之前必然有节点到达0后的节点
                end = maxPosition; //此时的maxPosition就是  上一个临界之后 一直到 end之间的节点能跳到的最远位置，
                steps++; //显然最少只需要一次跳跃
            }
        }
        return steps;
    }
}
